//
// Created by user on 2022/3/7.
//
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string minWindow(string s, string t) {
    int left=0;
    int right = 0;
    vector<int> cntT(60, 0); //26个小写 26个大写 8个其他字符
    int uniqueCharsInT = 0; //统计t中不同字符个数
    for (char c:t){
        if(cntT[c-'A']==0){uniqueCharsInT++;}
        cntT[c-'A']++;
    }
    //窗口中每个字符出现的次数
    vector<int> windowCnts(60, 0);
    //记录当前窗口中字符出现的次数和t中字符出现的次数相等的字符数
    int matchedChars = 0;
    vector<int> ans{-1, 0, 0}; //最小长度，左边界和有边界
    while (right<s.size()){
        char rightChar = s[right];
        int rightCharIndex = rightChar-'A';
        windowCnts[rightCharIndex]++;
        if(windowCnts[rightCharIndex]==cntT[rightCharIndex]){
            matchedChars++;
        }
        while(left<=right && matchedChars==uniqueCharsInT){
            //缩减窗口大小，因为我们想找到最短符合条件的字串
            if(ans[0]==-1 || right-left+1<ans[0]){
                ans[0] = right-left+1;
                ans[1] = left;
                ans[2] = right;
            }
            char leftChar = s[left];
            int leftCharIndex = leftChar-'A';
            windowCnts[leftCharIndex]--;
            if(windowCnts[leftCharIndex]<cntT[leftCharIndex]){
                matchedChars--;
            }
            left++;
        }

        right++;

    }
    return ans[0]==-1?"":s.substr(ans[1], ans[2]-ans[1]+1);

}

int main(){

    minWindow("ADOBECODEBANC","ABC");

    return 0;
}